Thực đơn
Số_nguyên_tố_Mersenne Các định lý về số nguyên tố Mersennehay
( 2 a − 1 ) ⋅ ( 1 + 2 a + 2 2 a + 2 3 a + ⋯ + 2 ( b − 1 ) a ) = 2 a b − 1 {\displaystyle (2^{a}-1)\cdot \left(1+2^{a}+2^{2a}+2^{3a}+\dots +2^{(b-1)a}\right)=2^{ab}-1}nhờ đặt c = 2 a {\displaystyle c=2^{a}} , d = 1 {\displaystyle d=1} , và n = b {\displaystyle n=b}
Chứng minh:
( a − b ) ∑ k = 0 n − 1 a k b n − 1 − k {\displaystyle (a-b)\sum _{k=0}^{n-1}a^{k}b^{n-1-k}} = ∑ k = 0 n − 1 a k + 1 b n − 1 − k − ∑ k = 0 n − 1 a k b n − k {\displaystyle =\sum _{k=0}^{n-1}a^{k+1}b^{n-1-k}-\sum _{k=0}^{n-1}a^{k}b^{n-k}} = a n + ∑ k = 1 n − 1 a k b n − k − ∑ k = 1 n − 1 a k b n − k − b n {\displaystyle =a^{n}+\sum _{k=1}^{n-1}a^{k}b^{n-k}-\sum _{k=1}^{n-1}a^{k}b^{n-k}-b^{n}} = a n − b n {\displaystyle =a^{n}-b^{n}}Chứng minh
Do
( 2 a − 1 ) ⋅ ( 1 + 2 a + 2 2 a + 2 3 a + ⋯ + 2 ( b − 1 ) a ) = 2 a b − 1 {\displaystyle (2^{a}-1)\cdot \left(1+2^{a}+2^{2a}+2^{3a}+\dots +2^{(b-1)a}\right)=2^{ab}-1}Nếu n {\displaystyle n} không phải là nguyên tố, hoặc n = a b {\displaystyle n=ab} trong đó 1 < a , b < n {\displaystyle 1<a,b<n} . Do đó, 2 a − 1 {\displaystyle 2^{a}-1} là ước của 2 n − 1 {\displaystyle 2^{n}-1} , hoặc 2 n − 1 {\displaystyle 2^{n}-1} không là nguyên tố.
Chứng minh
Gọi q là ước nguyên tố của 2p - 1 ta có:
2 p ≡ 1 ( mod q ) {\displaystyle 2^{p}\equiv 1{\pmod {q}}} .Theo định lý nhỏ Fermat ta có:
2 q − 1 ≡ 1 ( mod q ) {\displaystyle 2^{q-1}\equiv 1{\pmod {q}}} .Từ đó ta có q là ước chung của 2p - 1 và 2q - 1 - 1, hay là gcd ( 2 p − 1 , 2 q − 1 − 1 ) > 1 {\displaystyle \gcd(2^{p}-1,2^{q-1}-1)>1} (*).
Ta xét bổ đề sau: Nếu a và b là hai số nguyên dương phân biệt thì gcd ( 2 a − 1 , 2 b − 1 ) = 2 gcd ( a , b ) − 1 {\displaystyle \gcd(2^{a}-1,2^{b}-1)=2^{\gcd(a,b)}-1} .
Thật vậy, giả sử gcd ( a , b ) = d {\displaystyle \gcd(a,b)=d} , suy ra a = k1d và b = k2d.
Suy ra:
2 a − 1 = 2 k 1 d − 1 = ( 2 d − 1 ) × A {\displaystyle 2^{a}-1=2^{k_{1}d}-1=\left(2^{d}-1\right)\times A} 2 b − 1 = 2 k 2 d − 1 = ( 2 d − 1 ) × B {\displaystyle 2^{b}-1=2^{k_{2}d}-1=\left(2^{d}-1\right)\times B}Tức là bổ đề ta đã đặt ra là đúng.
Từ bổ đề suy ra: gcd ( 2 p − 1 , 2 q − 1 − 1 ) = 2 gcd ( p , q − 1 ) − 1 {\displaystyle \gcd(2^{p}-1,2^{q-1}-1)=2^{\gcd(p,q-1)}-1} .
Giả sử gcd ( p , q − 1 ) = 1 {\displaystyle \gcd(p,q-1)=1} thì suy ra được gcd ( 2 p − 1 , 2 q − 1 − 1 ) = 1 {\displaystyle \gcd(2^{p}-1,2^{q-1}-1)=1} , mâu thuẫn với (*). Do đó ta phải có gcd ( p , q − 1 ) > 1 {\displaystyle \gcd(p,q-1)>1} . Do p là số nguyên tố nên gcd ( p , q − 1 ) = p {\displaystyle \gcd(p,q-1)=p} hay q - 1 = bp.
Do q là ước của Mp lẻ nên q lẻ, suy ra b = 2k hay q = 2kp + 1.
Do 2p ≡ 1 (mod q) nên 2p + 1 ≡ 2 (mod q), suy ra 2 p + 1 2 {\displaystyle 2^{\frac {p+1}{2}}} là căn bậc hai của 2 theo modulo (môđun) q, tức nó là nghiệm của:
x 2 ≡ 2 ( mod q ) {\displaystyle x^{2}\equiv 2{\pmod {q}}} .Theo luật tương hỗ bậc hai:
q ≡ ± 1 ( mod 8 ) {\displaystyle q\equiv \pm 1{\pmod {8}}} .Thực đơn
Số_nguyên_tố_Mersenne Các định lý về số nguyên tố MersenneLiên quan
Số nguyên tố Số nguyên Số người thiệt mạng trong thảm sát Nam Kinh Số nguyên tử Số nguyên tố chính quy Số nguyên tố cùng nhau Số nguyên tố Sophie Germain Số nguyên tố Mersenne Số nguyên tố Wolstenholme Số nguyên tố PalindromeTài liệu tham khảo
WikiPedia: Số_nguyên_tố_Mersenne http://mathworld.wolfram.com/ http://mathworld.wolfram.com/MersenneNumber.html http://mathworld.wolfram.com/MersennePrime.html http://mathworld.wolfram.com/news/2005-12-25/merse... http://taz.de/1/archiv/archiv/?dig=2005/03/11/a035... http://primes.utm.edu/mersenne/LukeMirror/biblio.h... http://primes.utm.edu/mersenne/index.html http://primes.utm.edu/notes/1257787.html http://primes.utm.edu/notes/756839.html http://tony.reix.free.fr/Mersenne/Mersenne8x3qy.pd...